package org.example.myleet.p938;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.TreeNode;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        Assert.isTrue(32 == solution.rangeSumBST(parse(new Integer[]{10,5,15,3,7,null,18}), 7, 15));
        Assert.isTrue(23 == solution.rangeSumBST(parse(new Integer[]{10,5,15,3,7,13,18,1,null,6}), 6, 10));
        Assert.isTrue(63 == solution.rangeSumBST(parse(new Integer[]{18,9,27,6,15,24,30,3,null,12,null,21}), 18, 24));
    }

    private static TreeNode parse(Integer[] input) {
        int idx = 0;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = new TreeNode(input[idx++]);
        stack.push(node);
        while (idx < input.length && !stack.isEmpty()) {
            List<TreeNode> nodes = new ArrayList<>();
            while (!stack.isEmpty()) {
                nodes.add(stack.pollLast());
            }
            for (TreeNode n : nodes) {
                Integer i;
                if (idx < input.length) {
                    i = input[idx++];
                    if (i != null) {
                        n.left = new TreeNode(i);
                        stack.push(n.left);
                    }
                }
                if (idx < input.length) {
                    i = input[idx++];
                    if (i != null) {
                        n.right = new TreeNode(i);
                        stack.push(n.right);
                    }
                }
            }
        }
        return node;
    }
}
